package Study2019.Dp;

/**
 * 动态规划之挖金矿
 * @author: leiwenkang02@meituan.com
 * @date: 2019/1/24
 * @time: 13:31
 */
public class MostGold {
    public static void main(String[] args) {
        MostGold mostGold = new MostGold();
        int[] g = {400, 500, 200, 300, 350};
        int[] p = {5, 5, 3, 4, 3};
        int result = mostGold.getMostGold(5, 10, g, p);
        System.out.println(result);
    }
    /*
    n是金矿数
    w是工人数
    g数组为每个金矿对应的金币数
    p数组为每个金矿需要的工人数
     */
    public int getMostGold(int n, int w, int[] g, int[] p) {
        //临时保存上一个格子的结果，i个工人数时，可以挖到的最大金币
        int[] preResults = new int[w + 1];
        //对应i个工人数，可以挖到的最大金币
        int[] results = new int[w + 1];

        //填充边界，第一个格子，也就是第一个金矿
        //0 0 0 0 0 400 400 400 400 400 400
        for (int i = 1; i <= w; i++) {
            if (i < p[0]) {
                preResults[i] = 0;
            } else {
                preResults[i] = g[0];
            }
        }

        //外层循环是金矿数量，内存循环是工人数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < p[i - 1]) {
                    results[j] = preResults[j];
                } else {
                    results[j] = Math.max(preResults[j], preResults[j - p[i - 1]] + g[i - 2]);
                }
            }
            //保留这次结果，为下一个格子使用
            preResults = results;
        }
        //返回工人数是w的时候,n个金矿的结果
        return results[w];
    }

}
